home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / scangen.me < prev    next >
Text File  |  1992-09-25  |  64KB  |  2,181 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .EQ
  380. delim off
  381. .EN
  382. .de FR
  383. .ft R
  384. .sz +2
  385. ..
  386. .b " "
  387. .sp 1c
  388. .ta 9c
  389. .ft R
  390. .sz 12
  391. \l'17.1c'
  392. .nf
  393.  
  394.  
  395.     Efficient Generation of
  396.     Table-Driven Scanners
  397.  
  398.     J. Grosch
  399.  
  400.  
  401. \l'17.1c'
  402. .sp 12.5c
  403. \l'17.1c'
  404. .ft H
  405. .nf
  406.     GESELLSCHAFT F\*UR MATHEMATIK
  407.     UND DATENVERARBEITUNG MBH
  408.  
  409.     FORSCHUNGSSTELLE F\*UR
  410.     PROGRAMMSTRUKTUREN
  411.     AN DER UNIVERSIT\*AT KARLSRUHE
  412. .r
  413. \l'17.1c'
  414. .bp
  415. .\" oh ''Scanner Generation'%'
  416. .\" eh ''Scanner Generation'%'
  417. .nr % 0
  418. .ce 99
  419. .sz 20
  420. .b " "
  421. .sp 2
  422. Project
  423. .sp
  424. .b "Compiler Generation"
  425. .sp
  426. .sz 12
  427. \l'15c'
  428. .sp
  429. .sz 16
  430. .b "Efficient Generation of Table-Driven Scanners"
  431. or
  432. .b "NFA to DFA Conversion in Practically Linear Time"
  433. .sp 2
  434. Josef Grosch
  435. .sp 2
  436. .sz 14
  437. May 24, 1987
  438. .sp
  439. .sz 12
  440. \l'15c'
  441. .sp 2
  442. Report No. 2
  443. .sp 2
  444. Copyright \(co 1987 GMD
  445. .sp 2
  446. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  447. Forschungsstelle an der Universit\*at Karlsruhe
  448. Vincenz-Prie\*snitz-Str. 1
  449. D-7500 Karlsruhe
  450. .ce 0
  451. .bp
  452. .de $p
  453. .sp 1.5
  454. .ne 2c
  455. .ps 10
  456. .if '\\$3'' \{\
  457. .ce
  458. .tr aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
  459. \fR\\$1\fP
  460. .tr aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz
  461. .\}
  462. .if '\\$3'1' \{\
  463. .ce
  464. .tr aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
  465. \fR\\$1\fP
  466. .tr aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz
  467. .\}
  468. .if '\\$3'2' \{\
  469. \fB\\$1\fP
  470. .\}
  471. .ps
  472. .sp 0.1
  473. ..
  474. .nr pp 10
  475. .nr sp 10
  476. .nr tp 10
  477. .\" nr $r 5.3    \" factor for vertical spacing
  478. .nr $r 12    \" factor for vertical spacing
  479. .nr $R \n($r
  480. .sz 10
  481. .EQ
  482. delim $$
  483. gsize 10
  484. gfont R
  485. .EN
  486. .ce 99
  487. .sz 12
  488. .b "Efficient Generation of Lexical Analysers"
  489. .sz 10
  490. .sp
  491. J. Grosch
  492. .i
  493. GMD Forschungsstelle an der Universit\*at Karlsruhe
  494. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  495. grosch@karlsruhe.gmd.de
  496. .he '''%'
  497. .bp 1
  498. .b
  499. SUMMARY
  500. .ce 0
  501. .lp
  502. .b
  503. General tools for the automatic generation of lexical analysers like
  504. LEX\*([<\*([[Les75\*(]]\*(>] convert a specification consisting of a set of regular expressions
  505. into a deterministic finite automaton. The main algorithms involved are
  506. subset construction, state minimization, and table compression.
  507. Even if these algorithms do not
  508. show their worst case time behaviour they are still quite expensive. This
  509. paper shows how to solve the problem in linear time for practical cases,
  510. thus resulting in a significant speed-up. The idea is to combine the
  511. automaton introduced by Aho and Corasick\*([<\*([[AhC75\*(]]\*(>] with the direct
  512. computation of an efficient table representation. Besides the algorithm we
  513. present experimental results of the scanner generator Rex\*([<\*([[Gro87a\*(]]\*(>]
  514. which uses this technique.
  515. .sp
  516. .lp
  517. KEY WORDS  lexical analysis  scanner generator
  518. .sh 1 Introduction
  519. .pp
  520. Today, there exist several tools to generate lexical analysers like e.g.
  521. LEX\*([<\*([[Les75\*(]]\*(>], flex\*([<\*([[Pax88\*(]]\*(>], GLA\*([<\*([[Heu86\*(],Wai86\*(]]\*(>],
  522. ALEX\*([<\*([[M\*os86\*(]]\*(>], or Mkscan\*([<\*([[HoL87\*(]]\*(>]. This
  523. indicates that the automatic implementation of scanners becomes accepted by
  524. today's compiler writers. In the past, the low performance of generated
  525. scanners in comparison to hand-written ones may have restricted the
  526. generation approach to prototyping applications. However, since newer
  527. results\*([<\*([[Gro87b\*(],Heu86\*(],Wai86\*(]]\*(>] show that generated
  528. scanners have reached the speed of hand-written ones 
  529. there is no argument against using automatically generated lexical analysers
  530. in production compilers.
  531. In the following we present an efficient algorithm to convert a scanner
  532. specification based on regular expressions into a deterministic finite
  533. automaton.
  534. .\" .pp
  535. .\" In compiler construction the run time of a scanner generator is not a crucial
  536. .\" problem. But following the "swiss army knife"
  537. .\" idea .[aho ullman principles 1977]. a
  538. .\" scanner generator can be used for a wide range of applications and thus
  539. .\" become a frequently used tool. In this case the generation time becomes
  540. .\" important because nobody would accept a turn around time of e.g. 10 minutes
  541. .\" and usually some iterations are needed to complete a task.
  542. .pp
  543. A specification of a scanner consists of a set of regular expressions (REs).
  544. Each RE usually describes a deterministic finite automaton (DFA) being able
  545. to recognize a token. The whole set of REs, however, usually specifies a
  546. nondeterministic finite automaton (NFA). To allow scanning to be done in
  547. linear time the NFA has to be converted into a DFA. This problem can be
  548. solved with well known algorithms for subset construction and state
  549. minimization\*([<\*([[ASU86\*(],WaG84\*(]]\*(>].
  550. In the worst case subset construction takes time $ O ( 2 sup n ) $ and
  551. state minimization $ O ( n sup 2 ) $ or 
  552. $ O ( n~log~n ) $ if n is the number of states.
  553. If the DFA is implemented as a table-driven automaton an additional
  554. algorithm for table-compression is needed in practice, usually taking time 
  555. $ O ( n sup 2 ) $.
  556. .(b
  557. .vs 12
  558. Running example:
  559. .sp 0.5
  560. .FT
  561. letter ( letter | digit ) *   \(-> IdentSymbol
  562. digit +                       \(-> DecimalSymbol
  563. octdigit + Q                  \(-> OctalSymbol
  564. BEGIN                         \(-> BeginSymbol
  565. END                           \(-> EndSymbol
  566. :=                            \(-> AssignSymbol
  567. .)b
  568. .(z
  569. .PS
  570. circlerad = circlerad/2
  571.  
  572. N0:    circle    "0"
  573.     arrow    "0-7" above
  574. N3:    circle    "3"
  575.     arrow    "Q" above
  576.     circle    "4"
  577. A3:    arc    from N3.e to N3.s at N3 + (arcrad * 0.7, - arcrad * 0.7) cw ->
  578.     "0-7"    at A3.e + (arcrad, 0) ljust
  579.  
  580. N5:    circle    "5" at N3 - (0, linewid)
  581.     arrow    " E" above
  582.     circle    "6"
  583.     arrow    "G" above
  584.     circle    "7"
  585.     arrow    "I" above
  586.     circle    "8"
  587.     arrow    "N" above
  588.     circle    "9"
  589.  
  590. N2:    circle    "2" at N3 + (0, linewid)
  591. A2:    arc    from N2.ne to N2.se at N2 + (arcrad, 0) cw <-
  592.     "0-9"    at A2.e + (arcrad, 0) ljust
  593.  
  594. N1:    circle    "1" at N2 + (0, linewid)
  595. A1:    arc    from N1.ne to N1.se at N1 + (arcrad, 0) cw <-
  596.     "A-Z,a-z,0-9" at A1.e + (arcrad, 0) ljust
  597.  
  598. N10:    circle    "10" at N5 - (0, linewid)
  599.     arrow    "N" above
  600.     circle    "11"
  601.     arrow    "D" above
  602.     circle    "12"
  603.  
  604. N13:    circle    "13" at N10 - (0, linewid)
  605.     arrow    "=" above
  606.     circle    "14"
  607.  
  608.     arrow    "A-Z,a-z " rjust from N0 to N1 chop
  609.     arrow    "  0-9"      ljust from N0 to N2 chop
  610.     arrow    "B"      above from N0 to N5 chop
  611.     arrow    " E"      above from N0 to N10 chop
  612.     arrow    " :"      above from N0 to N13 chop
  613. .PE
  614. .sp
  615. Fig. 1: NFA for the running example
  616. .)z
  617. .(z
  618. .PS
  619.  
  620. N0:    circle    "0"
  621.     line    invis
  622. DUMMY:    circle    invis
  623.  
  624. N5:    circle    "5" at DUMMY - (0, linewid * 2)
  625.     arrow    "E" above
  626. N6:    circle    "6"
  627.     arrow    "G" above
  628. N7:    circle    "7"
  629.     arrow    "I" above
  630. N8:    circle    "8"
  631.     arrow    "N" above
  632. N9:    circle    "9"
  633.  
  634. N13:    circle    "13" at N5 - (0, linewid)
  635.     arrow    "=" above
  636. N14:    circle    "14"
  637.  
  638. N10:    circle    "10" at DUMMY + (0, linewid * 2)
  639.     arrow    "N" above
  640. N11:    circle    "11"
  641.     arrow    "D" above
  642. N12:    circle    "12"
  643.  
  644. N3:    circle    "3" at N10 + (0, linewid)
  645.     arrow    "Q" above
  646.     circle    "4"
  647. A3:    arc    from N3.e to N3.s at N3 + (arcrad * 0.7, - arcrad * 0.7) cw ->
  648.     "0-7"    at A3.e + (arcrad, 0) ljust
  649.  
  650. N2:    circle    "2" at N3 + (0, linewid)
  651. A2:    arc    from N2.ne to N2.se at N2 + (arcrad, 0) cw <-
  652.     "0-9"    at A2.e + (arcrad, 0) ljust
  653.  
  654. N1:    circle    "1" at N7 + (0, linewid * 2)
  655. A1:    arc    from N1.e to N1.n at N1 + (arcrad * 0.7, arcrad * 0.7) ->
  656.     "A-Z,a-z,0-9" at A1.e + (arcrad, 0) ljust
  657.  
  658.     arrow    " 8-9"        ljust from N3 to N2 chop
  659.     arrow    "8-9 "        rjust from N0 to N2 chop
  660.     arrow    "0-7"              from N0 to N3 chop
  661.     arrow    " E"        ljust from N0 to N10 chop
  662.     arrow    "A,C,D,F-Z,a-z"    above from N0 to N1 chop
  663.     arrow    " B"        ljust from N0 to N5 chop
  664.     arrow    " :"        ljust from N0 to N13 chop
  665.  
  666.     arrow    " \(*a\\\\\\\\\\\\\\\\N" ljust from N10 to N1 chop
  667.     arrow    " \(*a\\\\\\\\\\\\\\\\D" ljust from N11 to N1 chop
  668.     arrow    " \(*a"          ljust from N12 to N1 chop
  669.     arrow    "\(*a\\\\\\\\\\\\\\\\E " rjust from N5 to N1 chop
  670.     arrow    "\(*a\\\\\\\\\\\\\\\\G"  rjust from N6 to N1 chop
  671.     arrow    " \(*a\\\\\\\\\\\\\\\\I" ljust from N7 to N1 chop
  672.     arrow    " \(*a\\\\\\\\\\\\\\\\N" ljust from N8 to N1 chop
  673.     arrow    "  \(*a"         ljust from N9 to N1 chop
  674. .PE
  675. .sp
  676. Fig. 2: DFA for the running example (\(*a \\\\\\\\ \(*b stands for A-Z,a-z,0-9 except \(*b)
  677. .)z
  678. .pp
  679. The above specification describes six tokens each by a RE using an abstract
  680. notation.
  681. The automaton for these tokens is a NFA whose graphical representation is
  682. shown in Figure 1.
  683. The conversion of this NFA to a DFA yields the automaton shown in Figure 2.
  684. .sp 0.5
  685. .ne 2c
  686. .lp
  687. .b "Definition 1:"
  688. constant RE
  689. .pp
  690. A RE consisting only of the concatenation of characters is called a
  691. .i constant
  692. RE. A constant RE contains no operators like  +  *  |  ?
  693. .pp
  694. The language of a constant RE contains exactly one word. In the above example
  695. the constant REs are:
  696. .(b
  697. .FT
  698. BEGIN  END  :=
  699. .)b
  700. .pp
  701. During the construction of tables for a DFA by hand we observed that the
  702. task was solvable easily and in linear time for constant REs. Common prefixes
  703. have simply to be factored out thus arriving at a DFA having a decision tree
  704. as its graphical representation. Only the few non-constant REs required real
  705. work.
  706. .pp
  707. Scanner specifications for languages like Modula or C usually contain 90%
  708. constant REs: 60% keywords and 30% delimiters.
  709. Only 10% are non-constant REs needed to specify identifiers, various
  710. constants, and comments (see Appendix 2 for an example).
  711. The languages Ada and Pascal are exceptions from
  712. this observation because keywords can be written in upper or lower case
  713. letters or in any mixture.
  714. .pp
  715. It would be nice to retain the linear time
  716. behaviour for constant REs and perform subset construction and state
  717. minimization only for the few non-constant REs.
  718. The following chapter describes how this can be achieved by first converting
  719. the NFA of the non-constant REs to a DFA and incrementally adding the
  720. constant REs afterwards.
  721. The results of this method are shown for the running example.
  722. Then we generalize the method to automata with several start states. We
  723. conclude with a comparison of some scanner generators and present
  724. experimental results.
  725. .sh 1 "The Method"
  726. .pp
  727. The basic idea is to combine the special automaton of Aho and
  728. Corasick\*([<\*([[AhC75\*(]]\*(>] with the so-called "comb-vector" or row
  729. displacement
  730. technique\*([<\*([[ASU86\*(]]\*(>] for the table representation. The automaton of
  731. Aho and Corasick, called a pattern matching machine, extends a usual DFA by a
  732. so-called failure function and was originally used to search for overlapping
  733. occurrences of several strings in a given text. This automaton can also be
  734. used to cope with a certain amount of nondeterminism.
  735. .pp
  736. To introduce the terminology needed we present a definition of our version
  737. of the automaton. We call it a
  738. .i "tunnel automaton"
  739. and the tunnel function used corresponds to the
  740. failure function of Aho and Corasick.
  741. The name tunnel automaton is motivated by the analogy to the tunnel effect
  742. from nuclear physics: Electrons can switch over to another orbit without
  743. supply of energy and the tunnel automaton can change its state without
  744. consumption of an input symbol.
  745. .sp 0.5
  746. .ne 2c
  747. .lp
  748. .b "Definition 2:"
  749. tunnel automaton
  750. .pp
  751. A
  752. .i "tunnel automaton"
  753. is an extension of a DFA and consists of:
  754. .TS
  755. ;
  756. l l l.
  757. StateSet    a finite set of states    
  758. FinalStates    a set of final states    FinalStates \(ib StateSet
  759. StartState    a distinguished start state    StartState \(mo StateSet
  760. Vocabulary    a finite set of input symbols    
  761. Control    the transition function    Control: StateSet \(mu Vocabulary \(-> StateSet
  762. NoState    a special state to denote undefined    NoState \(mo StateSet
  763. Semantics    a function mapping the states    Semantics: StateSet $ ->~2 sup Proc $
  764.       to subsets of a set of procedures    
  765. Tunnel    a function mapping states to states    Tunnel: StateSet \(-> StateSet
  766. .TE
  767. .pp
  768. A tunnel automaton usually works like a DFA: in each step it consumes a
  769. symbol and performs a state transition. Additionally the tunnel automaton is
  770. allowed to change from state $ s $ to state $ t~=~Tunnel~( s ) $ without
  771. consuming a symbol, if no transition is possible in state $ s $. In state
  772. $ t $ the same rules apply, so the automaton may change the state several
  773. times without consuming any symbols.
  774. After recognizing a token a semantic procedure associated with the final
  775. state is executed.
  776. Algorithm 1 formalizes the behaviour of a tunnel automaton.
  777. To guarantee the termination of the WHILE loop the StateStack is initialized
  778. with a special final state called DefaultState.
  779. .sp 0.5
  780. .(b L
  781. .vs 12
  782. \fBAlgorithm 1\fR: tunnel automaton
  783. .sp 0.5
  784. .FT
  785.    BEGIN
  786.       Push (StateStack , DefaultState)
  787.       Push (SymbolStack, Dummy       )
  788.       State  := StartState
  789.       Symbol := NextSymbol ()
  790.       LOOP
  791.          IF Control (State, Symbol) \(!= NoState THEN
  792.             State := Control (State, Symbol)
  793.             Push (StateStack , State )
  794.             Push (SymbolStack, Symbol)
  795.             Symbol := NextSymbol ()
  796.          ELSE
  797.             State := Tunnel (State)
  798.             IF State = NoState THEN EXIT END
  799.          END
  800.       END
  801.       WHILE NOT Top (StateStack) \(mo FinalStates DO
  802.          State := Pop (StateStack )
  803.          UnRead  (Pop (SymbolStack))
  804.       END
  805.       Semantics (Top (StateStack)) ()
  806.    END
  807. .)b
  808. .sp 0.5
  809. .pp
  810. Before we present the algorithm to compute the control function
  811. we need some more definitions:
  812. .sp 0.5
  813. .ne 2c
  814. .lp
  815. .b "Definition 3:"
  816. trace
  817. .pp
  818. The
  819. .i trace
  820. of a string is the sequence of states that a tunnel automaton passes
  821. through given the string as input. States at which the automaton does not
  822. consume a symbol are
  823. omitted. This includes the start state. If necessary we pad the trace with
  824. the value NoState (denoted by the character -) to adjust its length to the
  825. length of the string.
  826. .(b
  827. .\" vs 12
  828. Examples (computed by using the DFA of Fig. 2 as tunnel automaton):
  829. .TS
  830. ;
  831. l l l l.
  832. The trace of    IF    is    1  1
  833. The trace of    ENDIF    is    10  11  12  1  1
  834. The trace of    1789    is    3  3  2  2
  835. The trace of    777Q    is    3  3  3  4
  836. The trace of    ::=    is    13  -  -
  837. .TE
  838. .)b
  839. .ne 2c
  840. .lp
  841. .b "Definition 4:"
  842. ambiguous state
  843. .pp
  844. We call a state $ s $
  845. .i ambiguous
  846. (or ambiguously reachable)
  847. if there exist more than one string such that
  848. for each string the repeated execution of the control function (first loop
  849. in Algorithm 1) ends up in state $ s $.
  850. .pp
  851. Example: The states 1, 2, 3, and 4 of the DFA of Fig. 2 are ambiguous
  852. states.
  853. .sp
  854. .lp
  855. .b Method:
  856. Construction of a tunnel automaton from a given set of regular expressions
  857. .ip "Step 1:" 2c
  858. Convert the NFA for non-constant REs to a DFA using the usual algorithms for
  859. subset construction and state minimization\*([<\*([[ASU86\*(],WaG84\*(]]\*(>].
  860. .ip "Step 2:" 2c
  861. Extend the DFA to a tunnel automaton by setting $ Tunnel~( s ) $ to
  862. $ NoState $ for every state $ s $.
  863. .ip "Step 3:" 2c
  864. Compute the set of ambiguous states of the tunnel automaton.
  865. For convenience Appendix 1 contains an algorithm to compute the
  866. ambiguous states.
  867. .ip "Step 4:" 2c
  868. For every constant RE execute Step 5 which incrementally extends the tunnel
  869. automaton. Continue with Step 6.
  870. .ip "Step 5:" 2c
  871. Compute the trace of the string specified by the constant RE using the
  872. current tunnel automaton. We have to distinguish 4 cases:
  873. .ip "Case 1:" 2c
  874. The trace contains neither NoState nor ambiguous states:
  875. .\sp 0.5
  876. .(l
  877. .PS
  878. dist    = 0.7
  879.  
  880. T1:    "Let the trace be" ljust
  881.     line    right 1.5i invis
  882. S1:    circle    "$ s sub 1 $"
  883.     arrow
  884. S2:    circle    "$ s sub 2 $"
  885.     arrow    right 0.2i
  886.     line    right 0.3i invis "..."
  887.     arrow    right 0.2i
  888. Sn:    circle    "$ s sub n $"
  889.  
  890.     "Let the RE be"    ljust at T1 + (0, linewid * dist)
  891. A1:    "$ a sub 1 $"    at S1 + (0, linewid * dist)
  892. A2:    "$ a sub 2 $"    at S2 + (0, linewid * dist)
  893. An:    "$ a sub n $"    at Sn + (0, linewid * dist)
  894.  
  895.     "..." at 0.5 between A2 and An
  896. .PE
  897. .)l
  898. .\sp 0.5
  899. .ip " " 2c
  900. As the path for the RE already exists include (add) the semantics of RE to
  901. the semantics of $ s sub n $ and include $ s sub n $ into the set of final
  902. states.
  903. .ip "Case 2:" 2c
  904. The trace does not contain ambiguous states but it contains NoState:
  905. .\sp 0.5
  906. .(l
  907. .PS
  908. T1:    "Let the trace be" ljust
  909.     line    right 1.5i invis
  910. S1:    circle    "$ s sub 1 $"
  911.     arrow
  912. S2:    circle    "$ s sub 2 $"
  913.     arrow    right 0.2i
  914.     line    right 0.3i invis "..."
  915.     arrow    right 0.2i
  916. Si:    circle    "$ s sub i $"
  917.  
  918.     "New States" ljust at T1 - (0, linewid)
  919. Zi1:    circle    "$ z sub i+1 $" at Si + (linewid, -linewid)
  920.     arrow    right 0.2i
  921.     line    right 0.3i invis "..."
  922.     arrow    right 0.2i
  923. Zn:    circle    "$ z sub n $"
  924.  
  925. Si1:    "-" at Zi1 + (0, linewid)
  926. Sn:    "-" at Zn  + (0, linewid)
  927.  
  928.     arrow    from Si to Zi1 chop
  929.  
  930.     "Let the RE be"    ljust at T1 + (0, linewid * dist)
  931. A1:    "$ a sub 1 $"    at S1 + (0, linewid * dist)
  932. A2:    "$ a sub 2 $"    at S2 + (0, linewid * dist)
  933. Ai:    "$ a sub i $"    at Si + (0, linewid * dist)
  934. Ai1:    "$ a sub i+1 $" at Si1 + (0, linewid * dist)
  935. An:    "$ a sub n $"    at Sn + (0, linewid * dist)
  936.  
  937.     "..." at 0.5 between A2 and Ai
  938.     "..." at 0.5 between Ai1 and An
  939.     "..." at 0.5 between Si1 and Sn
  940. .PE
  941. .)l
  942. .\sp 0.5
  943. .ip " " 2c
  944. Let $ s sub i $ be the last state before NoState.
  945. Extend the path $ s sub 1 ,~... ,~s sub i $ by newly created states
  946. $ z sub i+1 , ... ,~z sub n $. Extend the control function to pass through the
  947. states $ z sub i+1 , ... ,~z sub n $ given the input
  948. $ a sub i+1 , ... ,~a sub n $ starting from state $ s sub i $. Set the
  949. semantics of the states $ z sub i+1 , ... ,~z sub n-1 $ to the empty set.
  950. Set the semantics of $ z sub n$ to the semantics of RE and include
  951. $ z sub n $ into the set of final states. Set the tunnel function of
  952. $ z sub i+1 , ... ,~z sub n $ to NoState.
  953. .ip "Case 3:" 2c
  954. The trace does not contain NoState but it contains ambiguous states:
  955. .\sp 0.5
  956. .(l
  957. .PS
  958. T1:    "Let the trace be" ljust
  959.     line    right 1.5i invis
  960. S1:    circle    "$ s sub 1 $"
  961.     arrow
  962. S2:    circle    "$ s sub 2 $"
  963.     arrow    right 0.2i
  964.     line    right 0.3i invis "..."
  965.     arrow    right 0.2i
  966. Si1:    circle    "$ s sub i-1 $"
  967.     arrow    dashed
  968. Si:    circle    "$ s sub i $"
  969.     arrow    right 0.2i
  970.     line    right 0.3i invis "..."
  971.     arrow    right 0.2i
  972. Sn:    circle    "$ s sub n $"
  973.  
  974.     "New States" ljust at T1 - (0, linewid)
  975. Zi:    circle    "$ z sub i $" at Si - (0, linewid)
  976.     arrow    right 0.2i
  977.     line    right 0.3i invis "..."
  978.     arrow    right 0.2i
  979. Zn:    circle    "$ z sub n $"
  980.  
  981.     arrow    from Si1 to Zi chop
  982.     arrow    from Zi to Si chop dotted
  983.     arrow    from Zn to Sn chop dotted
  984.  
  985.     "Let the RE be"    ljust at T1 + (0, linewid * dist)
  986. A1:    "$ a sub 1 $"    at S1 + (0, linewid * dist)
  987. A2:    "$ a sub 2 $"    at S2 + (0, linewid * dist)
  988. Ai1:    "$ a sub i-1 $" at Si1 + (0, linewid * dist)
  989. Ai:    "$ a sub i $"    at Si + (0, linewid * dist)
  990. An:    "$ a sub n $"    at Sn + (0, linewid * dist)
  991.  
  992.     "..." at 0.5 between A2 and Ai1
  993.     "..." at 0.5 between Ai and An
  994. .PE
  995. .)l
  996. .\sp 0.5
  997. .ip " " 2c
  998. Let $ s sub i $ be the first ambiguous state in the trace.
  999. Create new states $ z sub i , ... ,~z sub n $ and
  1000. extend the control function to pass through the
  1001. states $ z sub i , ... ,~z sub n $ given the input
  1002. $ a sub i , ... ,~a sub n $ starting from state $ s sub i-1 $. Note, that the
  1003. transition from $ s sub i-1 $ to $ s sub i $ on input $ a sub i $ is lost
  1004. this way. Set the
  1005. semantics of the states $ z sub i , ... ,~z sub n $ to the semantics of the
  1006. corresponding states $ s sub i , ... ,~s sub n $.
  1007. Include the semantics of RE to the semantics of $ z sub n $ and include
  1008. $ z sub n $ into the set of final states. Set the tunnel function of
  1009. $ z sub i , ... ,~z sub n $ to the corresponding states
  1010. $ s sub i , ... ,~s sub n $.
  1011. .ip "Case 4:" 2c
  1012. The trace contains ambiguous states as well as NoState:
  1013. .\sp 0.5
  1014. .lp
  1015. .PS
  1016. T1:    "Let the trace be" ljust
  1017.     line    right 1.5i invis
  1018. S1:    circle    "$ s sub 1 $"
  1019.     arrow
  1020. S2:    circle    "$ s sub 2 $"
  1021.     arrow    right 0.2i
  1022.     line    right 0.2i invis "..."
  1023.     arrow    right 0.2i
  1024. Si1:    circle    "$ s sub i-1 $"
  1025.     arrow    dashed
  1026. Si:    circle    "$ s sub i $"
  1027.     arrow    right 0.2i
  1028.     line    right 0.2i invis "..."
  1029.     arrow    right 0.2i
  1030. Sj:    circle    "$ s sub j $"
  1031.  
  1032.     "New States" ljust at T1 - (0, linewid)
  1033. Zi:    circle    "$ z sub i $" at Si - (0, linewid)
  1034.     arrow    right 0.2i
  1035.     line    right 0.2i invis "..."
  1036.     arrow    right 0.2i
  1037. Zj:    circle    "$ z sub j $"
  1038.     arrow
  1039. Zj1:    circle    "$ z sub j+1 $"
  1040.     arrow    right 0.2i
  1041.     line    right 0.2i invis "..."
  1042.     arrow    right 0.2i
  1043. Zn:    circle    "$ z sub n $"
  1044.  
  1045. Sj1:    "-" at Zj1 + (0, linewid)
  1046. Sn:    "-" at Zn  + (0, linewid)
  1047.  
  1048.     arrow    from Si1 to Zi chop
  1049.     arrow    from Zi to Si chop dotted
  1050.     arrow    from Zj to Sj chop dotted
  1051.  
  1052.     "Let the RE be"    ljust at T1 + (0, linewid * dist)
  1053. A1:    "$ a sub 1 $"    at S1 + (0, linewid * dist)
  1054. A2:    "$ a sub 2 $"    at S2 + (0, linewid * dist)
  1055. Ai1:    "$ a sub i-1 $" at Si1 + (0, linewid * dist)
  1056. Ai:    "$ a sub i $"    at Si + (0, linewid * dist)
  1057. Aj:    "$ a sub j $"    at Sj + (0, linewid * dist)
  1058. Aj1:    "$ a sub j+1 $" at Sj1 + (0, linewid * dist)
  1059. An:    "$ a sub n $"    at Sn + (0, linewid * dist)
  1060.  
  1061.     "..." at 0.5 between A2 and Ai1
  1062.     "..." at 0.5 between Ai and Aj
  1063.     "..." at 0.5 between Aj1 and An
  1064.     "..." at 0.5 between Sj1 and Sn
  1065. .PE
  1066. .\sp 0.5
  1067. .ip " " 2c
  1068. Let $ s sub i $ be the first ambiguous state in the trace.
  1069. Let $ s sub j $ be the last state before NoState.
  1070. Create new states $ z sub i , ... ,~z sub n $ and
  1071. extend the control function to pass through the
  1072. states $ z sub i , ... ,~z sub n $ given the input
  1073. $ a sub i , ... ,~a sub n $ starting from state $ s sub i-1 $. Note again
  1074. that the
  1075. transition from $ s sub i-1 $ to $ s sub i $ on input $ a sub i $ is lost
  1076. this way. Set the
  1077. semantics of the states $ z sub i , ... ,~z sub j $ to the semantics of the
  1078. corresponding states $ s sub i , ... ,~s sub j $.
  1079. Set the
  1080. semantics of the states $ z sub j+1 , ... ,~z sub n-1 $ to the empty set.
  1081. Set the semantics of $ z sub n $ to the semantics of RE and
  1082. include
  1083. $ z sub n $ into the set of final states. Set the tunnel function of
  1084. $ z sub i , ... ,~z sub j $ to the corresponding states
  1085. $ s sub i , ... ,~s sub j $ and set the tunnel function of the states
  1086. $ z sub j+1 , ... ,~z sub n $ to NoState.
  1087. .ip "Step 6:" 2c
  1088. If an unambiguous semantic function is desired convert
  1089. .(b
  1090. Semantics (s) = { $ p sub 1 ,~... ,~p sub n $ }     to     Semantics (s) = { $ p sub i $ }
  1091. .)b
  1092. .ip " " 2c
  1093. for all states s. We assume the procedures $ p sub 1 ,~... ,~p sub n $ to be
  1094. ordered totally with $ p sub i $ being the maximal (see below) procedure of
  1095. $ p sub 1 ,~... ,~p sub n $.
  1096. .sp 2
  1097. .lp
  1098. .(z L
  1099. .vs 12
  1100. \fBAlgorithm 2\fR: extend a tunnel automaton to recognize an additional constant RE
  1101. .sp 0.5
  1102. .FT
  1103. BEGIN
  1104.    State  := StartState
  1105.    Symbol := NextSymbol ()   /* reading the string specified by the constant RE */
  1106. .sp 0.5
  1107.    /* trace and do nothing */
  1108. .sp 0.5
  1109.    LOOP
  1110.       IF Control (State, Symbol) = NoState OR
  1111.          Symbol = EndOfInput OR
  1112.          Control (State, Symbol) \(mo AmbiguousStates THEN EXIT END
  1113.       State  := Control (State, Symbol)   /* trace */
  1114.       Symbol := NextSymbol ()
  1115.    END
  1116.    PreviousState := State
  1117. .sp 0.5
  1118.    /* trace and duplicate the path */
  1119. .sp 0.5
  1120.    LOOP
  1121.       IF Control (State, Symbol) \(!= NoState THEN
  1122.          IF Symbol = EndOfInput THEN EXIT END
  1123.          NewState := CreateState ()
  1124.          State := Control (State, Symbol)   /* trace */
  1125.          Control (PreviousState, Symbol) := NewState
  1126.          Semantics (NewState) := Semantics (State)
  1127.          Tunnel (NewState) := State
  1128.          PreviousState := NewState
  1129.          Symbol := NextSymbol ()
  1130.       ELSE
  1131.          IF Tunnel (State) = NoState THEN EXIT END
  1132.          State := Tunnel (State)
  1133.       END
  1134.    END
  1135. .sp 0.5
  1136.    /* extend the path */
  1137. .sp 0.5
  1138.    WHILE Symbol \(!= EndOfInput DO
  1139.       NewState := CreateState ()
  1140.       Control (PreviousState, Symbol) := NewState
  1141.       Semantics (NewState) := \(O/
  1142.       Tunnel (NewState) := NoState
  1143.       PreviousState := NewState
  1144.       Symbol := NextSymbol ()
  1145.    END
  1146. .sp 0.5
  1147.    /* process new final state */
  1148. .sp 0.5
  1149.    FinalStates := FinalStates \(cu { PreviousState }
  1150.    Semantics (PreviousState) := Semantics (PreviousState) \(cu Semantics (RE)
  1151. END
  1152. .)z
  1153. .pp
  1154. Algorithm 2 describes step 5 more precisely.
  1155. The problem of an ambiguous semantic function arises already in the
  1156. running example, as e.g. the string END matches both the REs for IdentSymbol
  1157. and EndSymbol.
  1158. Therefore state 12 of Fig. 2 would be associated with two semantic
  1159. procedures. The generators LEX and Rex for example turn the semantic
  1160. function into an unambiguous one by
  1161. considering the sequence of the REs in the given specification.
  1162. The REs and their associated
  1163. semantic actions are mapped to priorities in descending order. In case of
  1164. conflicts the semantic action with greatest priority is preferred. In other
  1165. words the procedures are ordered totally and the "maximal procedure" out of
  1166. several ones is selected.
  1167. .pp
  1168. A tunnel automaton extended using Algorithm 2 works correctly because of the
  1169. following reasons.
  1170. The constant REs are recognized correctly because of the construction used.
  1171. We construct a decision tree without any ambiguous states.
  1172. .pp
  1173. The non-constant REs are recognized correctly because: If the tunnel
  1174. automaton stops at a newly created state we have propagated the semantics of
  1175. the original final state to the new one. Otherwise the tunnel automaton uses
  1176. at most one tunnel transition and stops at exactly the same state as it
  1177. would have stopped at before. That is because of the construction of the tunnel
  1178. function. As we did not change the semantic function of previously existing
  1179. states, except in the case where we could use the state as final state of a
  1180. constant RE, the automaton behaves as before.
  1181. .pp
  1182. We call a tunnel automaton
  1183. .i minimal
  1184. if it has the minimal number of states to do its job, e. g. it must be able
  1185. to distinguish between different tokens using separate final states.
  1186. Without a formal proof we state that Algorithm 2 constructs a minimal
  1187. automaton if the given DFA was minimal.
  1188. The reason is that a tunnel automaton has the same number of states and
  1189. the same "structure" as a corresponding DFA except that many regular
  1190. transitions are replaced by a few tunnel transitions.
  1191. Compare for example the Figures 2 and 3.
  1192. .sh 1 Example
  1193. .pp
  1194. Algorithm 2 constructs for the running example the tunnel automaton depicted
  1195. in Fig. 3. The dotted arrows denote tunnel transitions.
  1196. The automaton in Fig. 3 is graphically similar to the one in Fig. 2: most of
  1197. the transitions leading to state 1 have been replaced by tunnel transitions.
  1198. However, note the difference: whereas a solid arrow of Fig. 2 stands for a
  1199. big set of transitions a dotted arrow of Fig. 3 denotes a single tunnel
  1200. transition, only. This is the key to the efficient representation of the
  1201. control and tunnel functions. As the control function corresponds to a
  1202. sparse matrix it can advantageously be implemented using the comb-vector
  1203. technique\*([<\*([[ASU86\*(]]\*(>]. The rows of a matrix are merged
  1204. into a single vector called Next. Two additional vectors called Base and
  1205. Check are necessary to accomplish the access of the original data.
  1206. The resulting data structure resembles
  1207. the merging of several combs into one. In combination with the above a
  1208. fourth array called Tunnel is used to compress the
  1209. table even more. This array corresponds directly to our tunnel function.
  1210. Fig. 4 shows some entries of the comb-vector for the running example. The
  1211. excerpt is restricted to the characters E, N, D.
  1212. .sp 0.5
  1213. .(b L
  1214. .sp
  1215. .PS
  1216. N0:    circle    "0"
  1217.     line    invis
  1218. DUMMY:    circle    invis
  1219.  
  1220. N5:    circle    "5" at DUMMY - (0, linewid * 2)
  1221.     arrow    "E" above
  1222. N6:    circle    "6"
  1223.     arrow    "G" above
  1224. N7:    circle    "7"
  1225.     arrow    "I" above
  1226. N8:    circle    "8"
  1227.     arrow    "N" above
  1228. N9:    circle    "9"
  1229.  
  1230. N13:    circle    "13" at N5 - (0, linewid)
  1231.     arrow    "=" above
  1232. N14:    circle    "14"
  1233.  
  1234. N10:    circle    "10" at DUMMY + (0, linewid * 2)
  1235.     arrow    "N" above
  1236. N11:    circle    "11"
  1237.     arrow    "D" above
  1238. N12:    circle    "12"
  1239.  
  1240. N3:    circle    "3" at N10 + (0, linewid)
  1241.     arrow    "Q" above
  1242.     circle    "4"
  1243. A3:    arc    from N3.e to N3.s at N3 + (arcrad * 0.7, - arcrad * 0.7) cw ->
  1244.     "0-7"    at A3.e + (arcrad, 0) ljust
  1245.  
  1246. N2:    circle    "2" at N3 + (0, linewid)
  1247. A2:    arc    from N2.ne to N2.se at N2 + (arcrad, 0) cw <-
  1248.     "0-9"    at A2.e + (arcrad, 0) ljust
  1249.  
  1250. N1:    circle    "1" at N7 + (0, linewid * 2)
  1251. A1:    arc    from N1.e to N1.n at N1 + (arcrad * 0.7, arcrad * 0.7) ->
  1252.     "A-Z,a-z,0-9" at A1.e + (arcrad, 0) ljust
  1253.  
  1254.     arrow    " 8-9"        ljust from N3 to N2 chop
  1255.     arrow    "8-9 "        rjust from N0 to N2 chop
  1256.     arrow    "0-7"              from N0 to N3 chop
  1257.     arrow    " E"        ljust from N0 to N10 chop
  1258.     arrow    "A,C,D,F-Z,a-z"    above from N0 to N1 chop
  1259.     arrow    " B"        ljust from N0 to N5 chop
  1260.     arrow    " :"        ljust from N0 to N13 chop
  1261.  
  1262.     arrow    from N10 to N1 chop dotted
  1263.     arrow    from N11 to N1 chop dotted
  1264.     arrow    from N12 to N1 chop dotted
  1265.     arrow    from N5 to N1 chop dotted
  1266.     arrow    from N6 to N1 chop dotted
  1267.     arrow    from N7 to N1 chop dotted
  1268.     arrow    from N8 to N1 chop dotted
  1269.     arrow    from N9 to N1 chop dotted
  1270. .PE
  1271. .sp
  1272. Fig. 3: tunnel automaton for the running example
  1273. .)b
  1274. .(z L
  1275. .TS
  1276. tab (;) center;
  1277. l c c c c r r r r r c r r r c
  1278. l | c | c | c | c | r | r | r | r | r | c | r | r | r | c
  1279. l | c | c | c | c | r | r | r | r | r | c | r | r | r | c.
  1280.      ;0;1;2;...;68;69;70;71;72;...;78;79;80;
  1281. _
  1282. Check;-;-;-;...; 0; 0; 1; 1;11;...; 0;10; 1;...
  1283. _
  1284. Next ;-;-;-;...; 1;10; 1; 1;12;...; 1;11; 1;...
  1285. _
  1286. .TE
  1287. .TS
  1288. tab (;) center;
  1289. l r r c r r r c
  1290. l | r | r | c | r | r | r | c
  1291. l | r | r | c | r | r | r | c.
  1292. State ;0;1;...;10;11;12
  1293. _
  1294. Base  ;0;2;...; 1; 4; 0;...
  1295. _
  1296. Tunnel;-;-;...; 1; 1; 1;...
  1297. _
  1298. .TE
  1299. .sp
  1300. .FT
  1301.           Control (State, Symbol) := IF   Check [Base [State] + Symbol] = State
  1302.                                      THEN Next  [Base [State] + Symbol]
  1303.                                      ELSE NoState
  1304. .FR
  1305. .sp
  1306. .ce 2
  1307. Fig. 4: comb vector data structure for the running example and access procedure
  1308. (for characters E, N, D only; ASCII codes: E=69, D=68, N=78)
  1309. .)z
  1310. .pp
  1311. An advantage of Algorithm 2 is that this data structure is computed in part
  1312. directly from the set of REs. There is no need to compute a complete
  1313. classical DFA first and to transform it into the above data structure using
  1314. time and space consuming table compression algorithms afterwards.
  1315. The construction of the comb-vector consists primarily of the computation of
  1316. the Base and the Tunnel values. For each state the Base value is determined
  1317. by a simple search algorithm which shows reasonable results and performance.
  1318. A clever computation of the Tunnel values is essential for a good table
  1319. compression. Its complexity is $ O ( n sup 2 c ) $ where n is the number of
  1320. states of the DFA and c is the cardinality of the character set. For each
  1321. state an other state has to be determined which can safely act as "Tunnel
  1322. state" and which saves a maximal number of transitions. It is sufficient to
  1323. perform this expensive algorithm for the few states created for non-constant
  1324. REs only. The Tunnel values for the states created for constant REs are
  1325. determined by Algorithm 2 in linear time.
  1326. .sh 1 "Several Start States"
  1327. .pp
  1328. Scanner generators like LEX and Rex offer the feature of so-called start
  1329. states to handle left context. In each start state a different set of REs
  1330. may be activated and there are special statements to change the current start
  1331. state. A scanner specification using several start
  1332. states is turned into an automaton with several start states.
  1333. Under these circumstances the construction algorithm for a tunnel automaton
  1334. becomes a little bit more complex.
  1335. We only mention the problems that arise from this extension.
  1336. .\" .sh 2 "Computation of Ambiguous States"
  1337. .pp
  1338. First we have to refine the computation of ambiguous states. Definition 4
  1339. is still valid saying that an ambiguous state must be reachable with more than one
  1340. string. Now we have to take into account that strings can be processed
  1341. starting from several start states. The difference of the refined algorithm
  1342. lies in the treatment of the states being direct successors of the start
  1343. states. Such a state becomes ambiguous if there exist more than one
  1344. transition from one start state. It is not sufficient if there are several
  1345. transitions but each one originates in a different start state.
  1346. .\" Appendix 2 gives the refined algorithm.
  1347. .\" .sh 2 "Definition of Start Sets"
  1348. .pp
  1349. If a constant RE should be recognized in a set of start states S we would
  1350. like to construct only one sequence of states which can be reached from all
  1351. members of S. This is because we want to create as few states as possible.
  1352. However, we have to be careful, because the trace of the RE could lead to a
  1353. state which can be reached from a start state t not contained in S. This
  1354. would erroneously allow the recognition of the RE also from start state t.
  1355. Therefore we have to construct several sequences of states or we have to
  1356. branch off an existing sequence in this case. To be able to do this we have
  1357. to know the set of start states a state can be reached from.
  1358. .\" .ne 2c
  1359. .\" .lp
  1360. .\" .b "Definition 5:"
  1361. .\" start set
  1362. .\" .pp
  1363. .\" The
  1364. .\" .i "start set"
  1365. .\" of a state s is the set of start states, from which s is
  1366. .\" reachable by a path of transitions.
  1367. .\" .pp
  1368. Step 5 of the construction of a tunnel automaton has to be extended not only
  1369. to consider ambiguous states but also to check whether the set of start
  1370. states S of the RE is a proper subset of the set of start states a state
  1371. in the trace can be reached from.
  1372. In this case a side branch with newly created states is necessary.
  1373. .\" .sh 2 "Recording Traces"
  1374. .pp
  1375. We extend a tunnel automaton to recognize a RE once for each corresponding
  1376. start state. Our aim is to use the same sequence of states constructed for
  1377. the first start state, but we have to check whether this is safely possible.
  1378. To be able to reuse a sequence of states we have to record it. For every
  1379. character (index) and every associated state t from the traces of the RE we
  1380. record the state actually used in the tunnel automaton as target state of
  1381. the current transition. This is either the state t or a newly created one.
  1382. .\" .pp
  1383. The construction method is now extended in the following way. For each
  1384. character index i of the RE the state t from the trace is examined. Whenever
  1385. possible the state recorded for i and t is reused.
  1386. .if 0 \{\
  1387. .sh 2 "Algorithm"
  1388. .pp
  1389. Algorithm 3 extends Algorithm 2 to handle several start
  1390. states. It has to be executed once for each start state a RE should be
  1391. recognized in. The required input consists of:
  1392. .(b
  1393. .\" vs 12
  1394. .TS
  1395. ;
  1396. l l.
  1397. RE    constant RE (string) accessed by function NextSymbol
  1398. StartState    current start state for RE
  1399. StartStates    complete set of start states for RE
  1400. StartSet    mapping: StateSet \(-> $ 2 sup StartStates $
  1401.      (precomputed according to Definition 5)
  1402. .TE
  1403. .)b
  1404. .sp 0.5
  1405. .(l L
  1406. .vs 12
  1407. \fBAlgorithm 3\fR: extend a tunnel automaton to recognize an additional constant RE
  1408. .sp 0.5
  1409. .FT
  1410. BEGIN
  1411.    State         := StartState
  1412.    Symbol        := NextSymbol ()
  1413.    Index         := 1
  1414.    PreviousState := State
  1415. .sp 0.5
  1416.    /* trace and reuse existing path */
  1417. .sp 0.5
  1418.    LOOP
  1419.       State := Control (State, Symbol) /* trace */
  1420.       IF Symbol = EndOfInput OR
  1421.          State = NoState OR
  1422.          State \(mo AmbiguousStates OR
  1423.          StartStates \(sb StartSet (State) THEN EXIT END
  1424.       NewState := Record (Index, State)
  1425.       IF NewState \(!= NoState THEN
  1426.          Control (PreviousState, Symbol) := NewState
  1427.       ELSE
  1428.          NewState := State
  1429.          Record (Index, State) := NewState
  1430.       END
  1431.       StartSet (NewState) := StartSet (NewState) \(cu { StartState }
  1432.       PreviousState := NewState
  1433.       Symbol := NextSymbol ()
  1434.       Index +:= 1
  1435.    END
  1436. .sp 0.5
  1437.    /* trace and duplicate the path */
  1438. .sp 0.5
  1439.    LOOP
  1440.       IF Symbol = EndOfInput THEN EXIT END
  1441.       State := Control (State, Symbol) /* trace */
  1442.       IF State \(!= NoState THEN
  1443.          NewState := Record (Index, State)
  1444.          IF NewState = NoState THEN
  1445.             NewState := CreateState ()
  1446.             Semantics (NewState) := Semantics (State)
  1447.             Tunnel (NewState) := State
  1448.             Record (Index, State) := NewState
  1449.          END
  1450.          Control (PreviousState, Symbol) := NewState
  1451.          StartSet (NewState) := StartSet (NewState) \(cu { StartState }
  1452.          PreviousState := NewState
  1453.          Symbol := NextSymbol ()
  1454.          Index +:= 1
  1455.       ELSE
  1456.          IF Tunnel (State) = NoState THEN EXIT END
  1457.          State := Tunnel (State)
  1458.       END
  1459.    END
  1460. .sp 0.5
  1461.    /* extend the path */
  1462. .sp 0.5
  1463.    WHILE Symbol \(!= EndOfInput DO
  1464.       NewState := Record (Index, NoState)
  1465.       IF NewState = NoState THEN
  1466.          NewState := CreateState ()
  1467.          Semantics (NewState) := \(O/
  1468.          Tunnel (NewState) := NoState
  1469.          Record (Index, NoState) := NewState
  1470.       END
  1471.       Control (PreviousState, Symbol) := NewState
  1472.       StartSet (NewState) := StartSet (NewState) \(cu { StartState }
  1473.       PreviousState := NewState
  1474.       Symbol := NextSymbol ()
  1475.       Index +:= 1
  1476.    END
  1477. .sp 0.5
  1478.    /* process new final state */
  1479. .sp 0.5
  1480.    FinalStates := FinalStates \(cu { PreviousState }
  1481.    Semantics (PreviousState) := Semantics (PreviousState) \(cu Semantics (RE)
  1482. END
  1483. .)l
  1484. .sp 0.5
  1485. .\}
  1486. .sh 1 "Experimental Results"
  1487. .pp
  1488. The presented method has been used in a scanner generator called
  1489. .i Rex
  1490. (Regular EXpression tool)
  1491. which is implemented by a 5,500 line Modula-2\*([<\*([[Wir85\*(]]\*(>] program.
  1492. It is able to generate
  1493. scanners in the languages C and Modula-2. The generated scanners are
  1494. table-driven implementations of a tunnel
  1495. automaton. In the following we compare the time to generate a scanner as
  1496. well as the speed of the generated scanners for LEX\*([<\*([[Les75\*(]]\*(>], flex\*([<\*([[Pax88\*(]]\*(>],
  1497. and Rex\*([<\*([[Gro87a\*(],Gro88\*(]]\*(>].
  1498. Flex is a rewrite of LEX intended to generate lexical analysers much faster
  1499. and the analysers use smaller tables and run faster.
  1500. .pp
  1501. To compare the scanner generators we used 4 versions of a Modula-2 scanner
  1502. specification (see Appendix 2 for an example written in the input language
  1503. of Rex). The versions differ in
  1504. the number of constant REs as shown in Table 1.
  1505. Version 1 is incomplete, version 2 omits keywords, version 3
  1506. has keywords, and version 4 has lower as well as upper case keywords.
  1507. The times are given in seconds measured on a MC 68020 processor.
  1508. The optimization of flex can be controlled by options: usually -cem results
  1509. in the smallest tables and -cf in the fastest analyser.
  1510. .(z C
  1511. .\" vs 12
  1512. \fBTable 1:\fP Comparison of Scanner Generators
  1513. .sp 0.5
  1514. .TS
  1515. tab (;) box center;
  1516. l s | c c c c
  1517. l s | r r r r
  1518. l s | r r r r
  1519. l s | r r r r
  1520. l s | r r r r
  1521. l s | r r r r
  1522. l s | r r r r
  1523. l l | r r r r.
  1524.                                     ;Spec. 1;Spec. 2;Spec. 3;Spec. 4
  1525. _
  1526. # of non-constant REs               ; 10; 10; 10; 10
  1527. # of constant REs                   ;  2; 29; 69;109
  1528. total # of REs                      ; 12; 39; 79;119
  1529. _
  1530. # of states for non-constant REs    ; 40; 40; 40; 40
  1531. # of states for constant REs        ;  0; 26;181;336
  1532. total # of states (generated by Rex); 40; 66;221;376
  1533. _
  1534. generation time using;LEX      ;3.14;6.71;73.71;215.08
  1535. [seconds]            ;flex -cem;0.69;0.78; 2.01;  3.81
  1536. .\"                     ;flex -cfe;0.69;1.12; 3.81;  8.60
  1537.                      ;flex -cf ;1.39;2.35; 7.16; 12.16
  1538.                      ;Rex      ;3.56;3.76; 4.91;  6.16
  1539. _
  1540. table size using     ;LEX      ; 2,996; 4,708;39,156;67,384
  1541. [bytes]              ;flex -cem; 1,116; 1,376; 2,868; 4,592
  1542. .\"                     ;flex -cfe; 2,016; 5,360;24,976;59,524
  1543.                      ;flex -cf ;10,744;17,424;57,260;97,096
  1544.                      ;Rex      ; 3,114; 3,218; 4,366; 5,530
  1545. _
  1546. scanner size using   ;LEX      ; 5,464; 8,044;43,756;73,264
  1547. [bytes]              ;flex -cem;14,240;15,368;18,140;21,144
  1548. .\"                     ;flex -cfe; 6,748;10,960;31,856;67,684
  1549.                      ;flex -cf ;15,452;23,000;64,116;105,232
  1550.                      ;Rex      ; 8,456; 8,884;11,200;13,536
  1551. .TE
  1552. .)z
  1553. .pp
  1554. LEX performs well for small specifications but it seems to use a quadratic
  1555. or exponential algorithm for all the REs. This
  1556. leads to long generation times and large tables for large specifications
  1557. (containing e. g. many keywords).
  1558. .pp
  1559. Flex is quite an improvement compared to LEX especially in terms of
  1560. generation time. The sizes of the tables and the generated scanners depend on
  1561. the optimization flags: -cem reduces the sizes drastically but -cf yields
  1562. sizes even larger than LEX.
  1563. .pp
  1564. The timings of Rex demonstrate its linear behaviour. In general the
  1565. generation times are not quite as small as those of flex except for
  1566. specification 4.
  1567. The expensive algorithms
  1568. for subset construction, state minimization, and table compression
  1569. are executed for 40 states, only. An arbitrary number of
  1570. constant REs like keywords can be added in a small, linear growing time.
  1571. Although the generated tables are larger than those of flex the total sizes
  1572. of the scanners (including the tables) are smaller.
  1573. Compared to LEX
  1574. the correct scanner specification 3 is processed nearly 20 times faster by
  1575. Rex, the size of the table is 10 times smaller, and
  1576. the scanner is 4 times smaller.
  1577. .(z C
  1578. .\" vs 12
  1579. \fBTable 2:\fP Comparison of Generated Scanners
  1580. .sp 0.5
  1581. .TS
  1582. tab (;) box center;
  1583. l | c s s s | c s
  1584. l | c s s s | c s
  1585. l | r r r r | r r.
  1586. generator;with hashing of identifiers and;without hashing and
  1587.          ;number conversion;number conversion
  1588. _
  1589.          ;table size;scanner size;time;speed;time;speed
  1590.          ;[bytes];[bytes];[sec.];[lines/min.];[sec.];[lines/min.]
  1591. _
  1592. LEX      ;39,156;43,756;7.21; 34,700;6.88; 36,400
  1593. flex -cem; 2,868;18,140;3.99; 62,700;3.69; 67,800
  1594. .\"flex -cfe;24,976;31,856;2.60; 96,300;2.29;109,300
  1595. flex -cf ;57,260;64,116;2.12;118,000;1.80;139,000
  1596. Rex -m   ; 4,306;13,672;3.00; 83,400;2.22;112,700
  1597. Rex -c   ; 4,366;11,200;1.77;141,400;1.37;182,700
  1598. .TE
  1599. .)z
  1600. .pp
  1601. To compare the generated scanners (Table 2) we used a big Modula-2 program
  1602. as input whose characteristics are as follows:
  1603. # of lines: 4,171, # of characters: 100,268, # of tokens: 16,948.
  1604. The timings include input from file, scanning and hashing of identifiers.
  1605. The Rex options -m and -c determine the target languages Modula-2 and C.
  1606. Compared to LEX flex yields a speed-up of 1.8 with options -cem and a
  1607. speed-up between 3.4 and 3.8 with options -cf. The C version of Rex reaches
  1608. a speed-up between 4 and 5. This speed is reached with analysers that are
  1609. considerable smaller than flex generated ones.
  1610. The figures show that a tunnel automaton can be implemented efficiently:
  1611. Scanners generated by Rex are 4 to 5 times faster than scanners generated by
  1612. LEX. More details can be found in reference\*([[Gro87b\*(]].
  1613. .(z C
  1614. .\" vs 12
  1615. \fBTable 3:\fP Comparison of Rex-Generated Scanners
  1616. .sp 0.5
  1617. .TS
  1618. tab (;) box center;
  1619. l | c s s s | c s
  1620. l | r r r r | r r.
  1621. language;generator data;scanner data
  1622. _
  1623.         ;static size;dyn. memory;total memory;time;table size;scanner size
  1624.         ;[bytes];[bytes];[bytes];[sec.];[bytes];[bytes]
  1625. _
  1626. Pascal  ;102,970;238,464;341,434; 87.40;4,426;13,128
  1627. Modula  ;102,970;201,344;304,314;  4.93;4,306;13,692
  1628. Oberon  ;102,970;201,344;304,314;  5.71;5,122;14,284
  1629. C       ;102,970;201,344;304,314;  7.24;5,702;13,296
  1630. Ada     ;102,970;441,984;544,954;300.63;6,222;17,450
  1631. .TE
  1632. .)z
  1633. .pp
  1634. Table 3 compares scanners for different languages generated by Rex.
  1635. The sizes of the tables and the complete scanners all lie in the same range
  1636. which is relatively small. Only the generation times for Pascal and Ada are
  1637. exceptionally long. The reason is that these languages allow keywords to be
  1638. written with any letters no matter if upper or lower case. Therefore
  1639. keywords are no longer constant REs and can not be processed with the
  1640. presented linear algorithm.
  1641. .sh 1 Conclusion
  1642. .pp
  1643. The presented method allows the conversion of a NFA given by a set of REs to a DFA
  1644. in practically linear time. This holds under the assumption that only a few
  1645. non-constant but many constant REs have to be processed which is true in
  1646. many practical cases. Compared to LEX we gained a speed-up of up to 20.
  1647. Compared to flex which similarly improves the generation times the
  1648. generated scanners are smaller and faster.
  1649. Not only is the generation time reduced drastically
  1650. but also the space requirement during generation of
  1651. the scanner. The generator has to perform the subset construction,
  1652. state minimization, and table compression only for a
  1653. few states. Therefore the space needed by those algorithms is small. The
  1654. presented method directly constructs a space efficient representation of the
  1655. scanner control table which is used in combination with the comb-vector
  1656. technique\*([<\*([[ASU86\*(]]\*(>].
  1657. The method allows the generation of lexical analysers in a small amount of
  1658. time.
  1659. .\" Therefore scanner generators can become tools for more purposes than
  1660. .\" just compiler construction.
  1661. The generated scanners are powerful and
  1662. efficient enough to be used in production compilers.
  1663. Finally, scanner generators could be applied to a broader area than
  1664. just compiler construction.
  1665. .fi
  1666. .sz 12
  1667. .[]
  1668. .[-
  1669. .ds [F AhC75
  1670. .ds [A A\*(p]\*(a]V\*(p] Aho
  1671. .as [A \*(n]M\*(p]\*(a]J\*(p] Corasick
  1672. .ds [T Efficient String Matching: An Aid to Bibliographic Search
  1673. .nr [P 1
  1674. .ds [P 333-340
  1675. .ds [J Comm. ACM
  1676. .ds [V 18
  1677. .ds [D June 1975
  1678. .ds [N 6
  1679. .][
  1680. .[-
  1681. .ds [F ASU86
  1682. .ds [A A\*(p]\*(a]V\*(p] Aho
  1683. .as [A \*(c]R\*(p] Sethi
  1684. .as [A \*(m]J\*(p]\*(a]D\*(p] Ullman
  1685. .ds [T Compilers: Principles, Techniques, and Tools
  1686. .ds [I Addison Wesley
  1687. .ds [C Reading, M\&A
  1688. .ds [D 1986
  1689. .][
  1690. .[-
  1691. .ds [F Gro87a
  1692. .ds [A J\*(p] Grosch
  1693. .ds [T Rex - A Scanner Generator
  1694. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1695. .ds [R Compiler Generation Report No. 5
  1696. .ds [N 5
  1697. .ds [D Dec. 1987
  1698. .][
  1699. .[-
  1700. .ds [F Gro87b
  1701. .ds [A J\*(p] Grosch
  1702. .ds [T An Efficient Table-Driven Scanner
  1703. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1704. .ds [R Compiler Generation Report No. 1
  1705. .ds [N 1
  1706. .ds [D May 1987
  1707. .][
  1708. .[-
  1709. .ds [F Gro88
  1710. .ds [A J\*(p] Grosch
  1711. .ds [T Selected Examples of Scanner Specifications
  1712. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1713. .ds [R Compiler Generation Report No. 7
  1714. .ds [N 7
  1715. .ds [D Mar. 1988
  1716. .][
  1717. .[-
  1718. .ds [F Heu86
  1719. .ds [A V\*(p]\*(a]P\*(p] Heuring
  1720. .ds [T The Automatic Generation of Fast Lexical Analysers
  1721. .nr [P 1
  1722. .ds [P 801-808
  1723. .ds [J Software\(emPractice & Experience
  1724. .ds [V 16
  1725. .ds [N 9
  1726. .ds [D Sep. 1986
  1727. .][
  1728. .[-
  1729. .ds [F HoL87
  1730. .ds [A R\*(p]\*(a]N\*(p] Horspool
  1731. .as [A \*(n]M\*(p]\*(a]R\*(p] Levy
  1732. .ds [T Mkscan - An Interactive Scanner Generator
  1733. .nr [P 1
  1734. .ds [P 369-378
  1735. .ds [J Software\(emPractice & Experience
  1736. .ds [V 17
  1737. .ds [N 6
  1738. .ds [D June 1987
  1739. .][
  1740. .[-
  1741. .ds [F Les75
  1742. .ds [A M\*(p]\*(a]E\*(p] Lesk
  1743. .ds [T LEX \(em A Lexical Analyzer Generator
  1744. .ds [R Computing Science Technical Report 39
  1745. .ds [I Bell Telephone Laboratories
  1746. .ds [C Murray Hill, NJ
  1747. .ds [D 1975
  1748. .][
  1749. .[-
  1750. .ds [F M\*os86
  1751. .ds [A H\*(p] M\\*:ossenb\\*:ock
  1752. .ds [T Alex - A Simple and Efficient Scanner Generator
  1753. .ds [J SI\&GPLAN Notices
  1754. .ds [V 21
  1755. .ds [N 12
  1756. .nr [P 1
  1757. .ds [P 139-148
  1758. .ds [D Dec. 1986
  1759. .][
  1760. .[-
  1761. .ds [F Pax88
  1762. .ds [A V\*(p] Paxson
  1763. .ds [T Flex - Manual Pages
  1764. .ds [I Public Domain Software
  1765. .ds [D 1988
  1766. .][
  1767. .[-
  1768. .ds [F WaG84
  1769. .ds [A W\*(p]\*(a]M\*(p] Waite
  1770. .as [A \*(n]G\*(p] Goos
  1771. .ds [T Compiler Construction
  1772. .ds [I Springer Verlag
  1773. .ds [C New York, NY
  1774. .ds [D 1984
  1775. .][
  1776. .[-
  1777. .ds [F Wai86
  1778. .ds [A W\*(p]\*(a]M\*(p] Waite
  1779. .ds [T The Cost of Lexical Analysis
  1780. .nr [P 1
  1781. .ds [P 473-488
  1782. .ds [J Software\(emPractice & Experience
  1783. .ds [V 16
  1784. .ds [N 5
  1785. .ds [D May 1986
  1786. .][
  1787. .[-
  1788. .ds [F Wir85
  1789. .ds [A N\*(p] Wirth
  1790. .ds [T Programming in Modula-2
  1791. .nr [P 0
  1792. .ds [P 202
  1793. .ds [I Springer Verlag
  1794. .ds [C Heidelberg
  1795. .ds [D 1985
  1796. .ds [O Third Edition
  1797. .][
  1798. .bp
  1799. .uh "Appendix 1"
  1800. .sp
  1801. .(l L
  1802. .vs 12
  1803. \fBAlgorithm 4\fR: ambiguous states of a tunnel automaton (with one start state)
  1804.  
  1805. .FT
  1806. BEGIN
  1807. .sp 0.5
  1808.    /* transition function using the tunnel function */
  1809. .sp 0.5
  1810.    PROCEDURE NextState (State, Symbol)
  1811.       BEGIN
  1812.          LOOP
  1813.             IF Control (State, Symbol) \(!= NoState THEN
  1814.                RETURN Control (State, Symbol)
  1815.             ELSE
  1816.                State := Tunnel (State)
  1817.                IF State = NoState THEN RETURN NoState END
  1818.             END
  1819.          END
  1820.       END
  1821. .sp 0.5
  1822.    /* compute the number of predecessors */
  1823. .sp 0.5
  1824.    FORALL State \(mo StateSet DO
  1825.       PredCount (State) := 0
  1826.    END
  1827. .sp 0.5
  1828.    FORALL State \(mo StateSet DO
  1829.       FORALL Symbol \(mo Vocabulary DO
  1830.          PredCount (NextState (State, Symbol)) +:= 1
  1831.       END
  1832.    END
  1833. .sp 0.5
  1834.    /* iteratively remove states with 1 predecessor */
  1835. .sp 0.5
  1836.    AmbiguousStates   := StateSet - { NoState }
  1837.    UnambiguousStates := { StartState }
  1838. .sp 0.5
  1839.    WHILE UnambiguousStates \(!= \(O/ DO
  1840.       State := SELECT UnambiguousStates
  1841.       UnambiguousStates -:= { State }
  1842.       AmbiguousStates   -:= { State }
  1843.       FORALL Symbol \(mo Vocabulary DO
  1844.          Successor := NextState (State, Symbol)
  1845.          IF PredCount (Successor) = 1 THEN
  1846.             UnambiguousStates \(cu:= { Successor }
  1847.          END
  1848.       END
  1849.    END
  1850. END
  1851. .)l
  1852. .if 0 \{\
  1853. .bp
  1854. .uh "Appendix 2"
  1855. .sp
  1856. .(l L
  1857. .vs 12
  1858. \fBAlgorithm 5\fR: ambiguous states (several start states)
  1859.  
  1860. .FT
  1861. BEGIN
  1862. .sp 0.5
  1863.    /* compute the number of predecessors */
  1864. .sp 0.5
  1865.    FORALL State \(mo StateSet DO                     /* initialize */
  1866.       PredCount (State) := 0
  1867.    END
  1868. .sp 0.5
  1869.    FORALL StartState \(mo StartStateSet DO           /* start states */
  1870.       FORALL State \(mo StateSet DO
  1871.          PredCount2 (State) := 0
  1872.       END
  1873.       FORALL Symbol \(mo Vocabulary DO
  1874.          PredCount2 (Control (StartState, Symbol)) +:= 1
  1875.       END
  1876.       FORALL State \(mo StateSet DO
  1877.          PredCount (State) := Max (PredCount (State), PredCount2 (State))
  1878.       END
  1879.    END
  1880. .sp 0.5
  1881.    FORALL State \(mo StateSet - StartStateSet DO     /* other states */
  1882.       FORALL Symbol \(mo Vocabulary DO
  1883.          PredCount (Control (State, Symbol)) +:= 1
  1884.       END
  1885.    END
  1886. .sp 0.5
  1887.    /* iteratively remove states with 1 predecessor */
  1888. .sp 0.5
  1889.    AmbiguousStates   := StateSet - { NoState }
  1890.    UnambiguousStates := StartStateSet
  1891. .sp 0.5
  1892.    WHILE UnambiguousStates \(!= \(O/ DO
  1893.       State := SELECT UnambiguousStates
  1894.       UnambiguousStates -:= { State }
  1895.       AmbiguousStates   -:= { State }
  1896.       FORALL Symbol \(mo Vocabulary DO
  1897.          Successor := Control (State, Symbol)
  1898.          IF PredCount (Successor) = 1 THEN
  1899.             UnambiguousStates \(cu:= { Successor }
  1900.          END
  1901.       END
  1902.    END
  1903. END
  1904. .)l
  1905. .\}
  1906. .bp
  1907. .uh "Appendix 2"
  1908. .lp
  1909. .sp 0.5
  1910. An example of a scanner specification for Modula-2 in Rex syntax:
  1911. .sp
  1912. .(l L
  1913. .vs 12
  1914. .FT
  1915. GLOBAL  { VAR NestingLevel: CARDINAL; }
  1916. .sp 0.5
  1917. BEGIN   { NestingLevel := 0; }
  1918. .sp 0.5
  1919. DEFAULT { Error ("illegal character:"); yyEcho; }
  1920. .sp 0.5
  1921. EOF     { IF yyStartState = comment THEN Error ("unclosed comment"); END; }
  1922. .sp 0.5
  1923. DEFINE
  1924. .sp 0.5
  1925.    digit        = {0-9}         .
  1926.    letter       = {a-z A-Z}     .
  1927.    cmt          = - {*(\\t\\n}    .
  1928. .sp 0.5
  1929. START   comment
  1930. .sp 0.5
  1931. RULES
  1932. .sp 0.5
  1933.            "(*"         : {INC (NestingLevel); yyStart (comment);}
  1934. #comment#  "*)"         : {DEC (NestingLevel); IF NestingLevel = 0 THEN yyStart (STD); END;}
  1935. #comment#  "(" | "*" | cmt + : {}
  1936. .sp 0.5
  1937. #STD# digit +           ,
  1938. #STD# digit + / ".."    : {RETURN 1;}
  1939. #STD# {0-7} + B         : {RETURN 2;}
  1940. #STD# {0-7} + C         : {RETURN 3;}
  1941. #STD# digit {0-9 A-F} * H : {RETURN 4;}
  1942. #STD# digit + "." digit * (E {+\\-} ? digit +) ? : {RETURN 5;}
  1943. .sp 0.5
  1944. #STD# ' - {\\n'} * '     |
  1945.       \\" - {\\n"} * \\"   : {RETURN 6;}
  1946. .sp 0.5
  1947. #STD# ":"               : {RETURN 7;}
  1948. #STD# "="               : {RETURN 8;}
  1949. #STD# ":="              : {RETURN 9;}
  1950. \&...
  1951. .sp 0.5
  1952. #STD# AND               : {RETURN 34;}
  1953. #STD# ARRAY             : {RETURN 35;}
  1954. #STD# BEGIN             : {RETURN 36;}
  1955. \&...
  1956. .sp 0.5
  1957. #STD# letter (letter | digit) * : {RETURN 74;}
  1958. .)l
  1959.  
  1960.  
  1961. .if 0 \{\
  1962. .(l L
  1963. .vs 12
  1964. .FT
  1965. GLOBAL  { VAR NestingLevel: CARDINAL; }
  1966. .sp 0.5
  1967. BEGIN   { NestingLevel := 0; }
  1968. .sp 0.5
  1969. EOF     { IF yyStartState = comment THEN Error ("unclosed comment"); END; }
  1970. .sp 0.5
  1971. DEFINE
  1972. .sp 0.5
  1973.    digit        = {0-9}         .
  1974.    letter       = {a-z A-Z}     .
  1975.    cmt          = - {*(\\t\\n}    .
  1976. .sp 0.5
  1977. START   comment
  1978. .sp 0.5
  1979. RULES
  1980. .sp 0.5
  1981.            "(*"         : {INC (NestingLevel); yyStart (comment);}
  1982. #comment#  "*)"         : {DEC (NestingLevel); IF NestingLevel = 0 THEN yyStart (STD); END;}
  1983. #comment#  "(" | "*" | cmt + : {}
  1984. .sp 0.5
  1985. #STD# digit +           ,
  1986. #STD# digit + / ".."    : {RETURN 1;}
  1987. #STD# {0-7} + B         : {RETURN 2;}
  1988. #STD# {0-7} + C         : {RETURN 3;}
  1989. #STD# digit {0-9 A-F} * H : {RETURN 4;}
  1990. #STD# digit + "." digit * (E {+\\-} ? digit +) ? : {RETURN 5;}
  1991. .sp 0.5
  1992. #STD# ' - {\\n'} * '     |
  1993.       \\" - {\\n"} * \\"   : {RETURN 6;}
  1994. .sp 0.5
  1995. #STD# "#"               : {RETURN 7;}
  1996. #STD# "&"               : {RETURN 8;}
  1997. #STD# "("               : {RETURN 9;}
  1998. #STD# ")"               : {RETURN 10;}
  1999. #STD# "*"               : {RETURN 11;}
  2000. #STD# "+"               : {RETURN 12;}
  2001. #STD# ","               : {RETURN 13;}
  2002. #STD# "-"               : {RETURN 14;}
  2003. #STD# "."               : {RETURN 15;}
  2004. #STD# ".."              : {RETURN 16;}
  2005. #STD# "/"               : {RETURN 17;}
  2006. #STD# ":"               : {RETURN 18;}
  2007. #STD# ":="              : {RETURN 19;}
  2008. #STD# ";"               : {RETURN 20;}
  2009. #STD# "<"               : {RETURN 21;}
  2010. #STD# "<="              : {RETURN 22;}
  2011. #STD# "<>"              : {RETURN 23;}
  2012. #STD# "="               : {RETURN 24;}
  2013. #STD# ">"               : {RETURN 25;}
  2014. #STD# ">="              : {RETURN 26;}
  2015. #STD# "["               : {RETURN 27;}
  2016. #STD# "]"               : {RETURN 28;}
  2017. #STD# "^"               : {RETURN 29;}
  2018. #STD# "{"               : {RETURN 30;}
  2019. #STD# "|"               : {RETURN 31;}
  2020. #STD# "}"               : {RETURN 32;}
  2021. #STD# "~"               : {RETURN 33;}
  2022. .sp 0.5
  2023. #STD# AND               : {RETURN 34;}
  2024. #STD# ARRAY             : {RETURN 35;}
  2025. #STD# BEGIN             : {RETURN 36;}
  2026. #STD# BY                : {RETURN 37;}
  2027. #STD# CASE              : {RETURN 38;}
  2028. #STD# CONST             : {RETURN 39;}
  2029. #STD# DEFINITION        : {RETURN 40;}
  2030. #STD# DIV               : {RETURN 41;}
  2031. #STD# DO                : {RETURN 42;}
  2032. #STD# ELSE              : {RETURN 43;}
  2033. #STD# ELSIF             : {RETURN 44;}
  2034. #STD# END               : {RETURN 45;}
  2035. #STD# EXIT              : {RETURN 46;}
  2036. #STD# EXPORT            : {RETURN 47;}
  2037. #STD# FOR               : {RETURN 48;}
  2038. #STD# FROM              : {RETURN 49;}
  2039. #STD# IF                : {RETURN 50;}
  2040. #STD# IMPLEMENTATION    : {RETURN 51;}
  2041. #STD# IMPORT            : {RETURN 52;}
  2042. #STD# IN                : {RETURN 53;}
  2043. #STD# LOOP              : {RETURN 54;}
  2044. #STD# MOD               : {RETURN 55;}
  2045. #STD# MODULE            : {RETURN 56;}
  2046. #STD# \\NOT              : {RETURN 57;}
  2047. #STD# OF                : {RETURN 58;}
  2048. #STD# OR                : {RETURN 59;}
  2049. #STD# POINTER           : {RETURN 60;}
  2050. #STD# PROCEDURE         : {RETURN 61;}
  2051. #STD# QUALIFIED         : {RETURN 62;}
  2052. #STD# RECORD            : {RETURN 63;}
  2053. #STD# REPEAT            : {RETURN 64;}
  2054. #STD# RETURN            : {RETURN 65;}
  2055. #STD# SET               : {RETURN 66;}
  2056. #STD# THEN              : {RETURN 67;}
  2057. #STD# TO                : {RETURN 68;}
  2058. #STD# TYPE              : {RETURN 69;}
  2059. #STD# UNTIL             : {RETURN 70;}
  2060. #STD# VAR               : {RETURN 71;}
  2061. #STD# WHILE             : {RETURN 72;}
  2062. #STD# WITH              : {RETURN 73;}
  2063. .sp 0.5
  2064. #STD# letter (letter | digit) * : {RETURN 74;}
  2065. .sp 0.5
  2066. #STD# ANY               : {Error ("illegal character");}
  2067. .)l
  2068.  
  2069.  
  2070. .(l L
  2071. .vs 12
  2072. .FT
  2073.    digit   [0-9]
  2074.    letter  [a-zA-Z]
  2075.    CMT     [^*(]
  2076.    STR1    [\\t !-&(-~]
  2077.    STR2    [\\t !#-~]
  2078.  
  2079.    %Start  comment
  2080.  
  2081.    %%
  2082.                            int NestingLevel = 0;
  2083.  
  2084.    "(*"{CMT}*              {NestingLevel ++; BEGIN comment;}
  2085.    <comment>"*)"           {NestingLevel --; if (NestingLevel == 0) BEGIN 0;}
  2086.    <comment>"("            |
  2087.    <comment>"*"            |
  2088.    <comment>{CMT}+         ;
  2089.  
  2090.    " "*                    ;
  2091.    \\n                      ;
  2092.    \\t                      ;
  2093.  
  2094.    {digit}+                |
  2095.    {digit}+/".."           return 1;
  2096.    [0-7]+B                 return 2;
  2097.    [0-7]+C                 return 3;
  2098.    {digit}[0-9A-F]*H       return 4;
  2099.    {digit}+"."{digit}*(E[+-]?{digit}+)?    return 5;
  2100.  
  2101.    '{STR1}*'               |
  2102.    \\"{STR2}*\\"             return 6;
  2103.  
  2104.    "#"                     return 7;
  2105.    "&"                     return 8;
  2106.    "("                     return 9;
  2107.    ")"                     return 10;
  2108.    "*"                     return 11;
  2109.    "+"                     return 12;
  2110.    ","                     return 13;
  2111.    "-"                     return 14;
  2112.    "."                     return 15;
  2113.    ".."                    return 16;
  2114.    "/"                     return 17;
  2115.    ":"                     return 18;
  2116.    ":="                    return 19;
  2117.    ";"                     return 20;
  2118.    "<"                     return 21;
  2119.    "<="                    return 22;
  2120.    "<>"                    return 23;
  2121.    "="                     return 24;
  2122.    ">"                     return 25;
  2123.    ">="                    return 26;
  2124.    "["                     return 27;
  2125.    "]"                     return 28;
  2126.    "^"                     return 29;
  2127.    "{"                     return 30;
  2128.    "|"                     return 31;
  2129.    "}"                     return 32;
  2130.    "~"                     return 33;
  2131.  
  2132.    AND                     return 34;
  2133.    ARRAY                   return 35;
  2134.    BEGIN                   return 36;
  2135.    BY                      return 37;
  2136.    CASE                    return 38;
  2137.    CONST                   return 39;
  2138.    DEFINITION              return 40;
  2139.    DIV                     return 41;
  2140.    DO                      return 42;
  2141.    ELSE                    return 43;
  2142.    ELSIF                   return 44;
  2143.    END                     return 45;
  2144.    EXIT                    return 46;
  2145.    EXPORT                  return 47;
  2146.    FOR                     return 48;
  2147.    FROM                    return 49;
  2148.    IF                      return 50;
  2149.    IMPLEMENTATION          return 51;
  2150.    IMPORT                  return 52;
  2151.    IN                      return 53;
  2152.    LOOP                    return 54;
  2153.    MOD                     return 55;
  2154.    MODULE                  return 56;
  2155.    NOT                     return 57;
  2156.    OF                      return 58;
  2157.    OR                      return 59;
  2158.    POINTER                 return 60;
  2159.    PROCEDURE               return 61;
  2160.    QUALIFIED               return 62;
  2161.    RECORD                  return 63;
  2162.    REPEAT                  return 64;
  2163.    RETURN                  return 65;
  2164.    SET                     return 66;
  2165.    THEN                    return 67;
  2166.    TO                      return 68;
  2167.    TYPE                    return 69;
  2168.    UNTIL                   return 70;
  2169.    VAR                     return 71;
  2170.    WHILE                   return 72;
  2171.    WITH                    return 73;
  2172.  
  2173.    {letter}({letter}|{digit})*     return 74;
  2174. .)l
  2175. .\}
  2176. .bp 1
  2177. .lp
  2178. .b Contents
  2179. .sp
  2180. .xp
  2181.